package slidewindow;

/**
 * 本题涉及到dp及滑动窗口优化
 * https://leetcode-cn.com/problems/new-21-game/solution/javani-xiang-dong-tai-gui-hua-jie-jue-shuang-100-b/
 */
public class 新21点_837 {
    // 动态规划 + 滑动窗口
    // 求起始概率  反向递推  x 有 1/w 概率变为 x + 1 , x + 2, ... , x + w中的一个
    // dp[x] = dp[x+1]/w + dp[x+2]/w  + ... + dp[x+w]/w
    public double new21Game(int N, int K, int W) {
        // 先判断 K - 1 + W 是否在 N 的里面，如果在的话，说明肯定能赢得游戏，返回 1.0，也就是 100%
        if (N - K + 1 >= W) {
            return 1.0;
        }
        // k - 1时  最大还能 + w
        double[] dp = new double[K + W];
        // 将能赢得游戏的点数的概率设置为 1
        for (int i = K; i <= N; i++) {
            dp[i] = 1.0;
        }
        // 计算K + W 这几个点数的概率和
        double sumProb = N - K + 1;
        // 从 K - 1 开始计算，
        for (int i = K - 1; i >= 0; i--) {
            // 点数为 i 的赢得游戏的概率为 i + 1 ~ i + W 的概率和除以 W
            dp[i] = sumProb / W;
            sumProb = sumProb - dp[i + W] + dp[i];
        }

        return dp[0];

    }

    public static void main(String[] args) {
        新21点_837 n21 = new 新21点_837();
        double v = n21.new21Game(6, 1, 10);
        System.out.println(v);
    }
}
